Progress of virtualization technologies has extended applicability of the virtualization technologies not only in the field of cloud computing but also in the field of communication networks. For example, the 5th generation mobile communication networks conceptualize flexible network control by application of the virtualization technologies. In virtualization of communication networks, the NFV (Network Functions Virtualization) technology enables to provide service functions of a communication service provider as software on general-purpose servers, which have conventionally been implemented by dedicated hardware such as routers and gateways. Therefore, a service function becomes executable on any server that exists on the network. Also, the SFC (Service Function Chaining) technology enables to transmit a packet flow of a user to a designated service function in a designated order, and thereby, enables to readily combine service functions. By utilizing these virtualization technologies, a service provider can provide flexible services by readily utilizing network resources and service functions prepared in advance on a communication network.
Meanwhile, a network provider who carries out operational management of such a communication network allocates network resources of its own to a service based on a request from a service provider. In order to raise investment efficiency of facilities, it is important for the network provider to hold as many services as possible on the invested physical network resources.
Allocation of physical network resources to requested services is called “VNE (Virtual Network Embedding) problem”, on which a significant number of researches have been reported in recent years (e.g., Non-patent document 1, Non-patent document 2, Patent document 1, etc.). The VNE problem is a problem of allocating physical network resources to services such that requirements of the services are satisfied, in which a given physical network is modeled as a weighted, undirected graph. A physical network is constituted with transfer nodes represented by routers, service nodes to execute service functions, and links that connect these nodes. Service nodes are assumed to be scattered all over the network rather than located in an aggregated site such as a cloud. Among various resource allocation policies that have been proposed, the most frequently used one is minimization of resource usage. In terms of physical resources to be allocated, it is often the case that the link bandwidth between transfer nodes, the CPU, memory, and storage of a service node, and the like are taken into account. Requirements for each service include transfer bandwidth, the upper bound of transfer latency, types and order of service functions to be received on the way. The above-mentioned physical resources are allocated in a way to satisfy such requirements.
In Non-patent document 1 and Non-patent document 2, although parameters taken into consideration are different, the objective is to minimize physical resources to allocate. In Patent document 1, network links and servers having greater numbers of residual resources (having lighter loads) are prioritized when allocated to a service so as to equalize the entire resource allocation.